
/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REP�BLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE M�rida - Ministerio de Ciencia y Tecnolog�a

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph is distributed in the hope that it will be useful, but WITHOUT
  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REP�BLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Consejo Nacional de Investigaciones Cientificas y Tecnologicas 
    (CONICIT)
  - Fundacite M�rida
*/

# ifndef TPL_LIST_GRAPH_H
# define TPL_LIST_GRAPH_H

# include <memory>
# include <bitArray.H>
# include <tpl_dynArray.H>
# include <dyn_sort_utils.H>
# include <tpl_dynAvlTree.H>
# include <tpl_dynDlist.H>
# include <tpl_treapRk.H>

    /* macros para nodos */
# define NUM_ARCS(p)             ((p)->num_arcs)
# define NODE_BITS(p)            ((p)->control_bits)
# define NODE_COUNTER(p)         ((p)->counter)
# define IS_NODE_VISITED(p, bit) (NODE_BITS(p).get_bit(bit))
# define ARCS_LIST(p)            ((p)->arc_list) 
# define NODE_COOKIE(p)          ((p)->cookie) 

    /* macros para arcos */
# define ARC_COUNTER(p)         ((p)->counter)
# define ARC_BITS(p)            ((p)->control_bits)
# define IS_ARC_VISITED(p, bit) (ARC_BITS(p).get_bit(bit))
# define ARC_COOKIE(p)          ((p)->cookie) 

using namespace Aleph;

namespace Aleph {

template <typename Node_Info> class Graph_Node; 

template <typename Arc_Info> class Graph_Arc; 

class Arc_Node;

template <typename GT> class Path;

template <typename __Graph_Node, typename __Graph_Arc> class List_Graph;

template <typename __Graph_Node, typename __Graph_Arc> struct List_Digraph;

template <typename GT> class Mat_Graph;

template <typename MT, typename Entry_Info, typename Copy> class Ady_MaT;

static const long No_Visited = 0; // nodo o arco no ha sido visitado

enum Graph_Bits 
  {
    Depth_First, /// Bit de b�squeda en profundidad 
    Breath_First, /// Bit de b�squeda en amplitud
    Test_Cycle,  /// Bit de verificaci�n de ciclo
    Is_Acyclique, /// Bit de prueba de aciclicidad
    Test_Path, /// Bit de prueba de existencia de camino
    Find_Path, /// Bit de b�squeda de camino
    Kruskal, /// Bit de algoritmo de Kruskal
    Prim, /// Bit de algoritmo de Prim
    Dijkstra, /// Bit de algoritmo de Dijkstra
    Euler, /// Bit de camino euleriano
    Hamilton, /// Bit de camino hamiltoniano
    Spanning_Tree, // Bit de �rbol abarcador
    Build_Subtree, // Bit de construcci�n de subgrafos

    Num_Bits_Graph
  };

struct Bit_Fields
{
  unsigned int depth_first    : 1; /// Bit de b�squeda en profundidad 
  unsigned int breath_first   : 1; /// Bit de b�squeda en amplitud
  unsigned int test_cycle     : 1; /// Bit de verificaci�n de ciclo
  unsigned int is_acyclique   : 1; /// Bit de prueba de aciclicidad
  unsigned int test_path      : 1; /// Bit de prueba de existencia de camino
  unsigned int find_path      : 1; /// Bit de b�squeda de camino
  unsigned int kruskal        : 1; /// Bit de algoritmo de Kruskal
  unsigned int prim           : 1; /// Bit de algoritmo de Prim
  unsigned int dijkstra       : 1; /// Bit de algoritmo de Dijkstra
  unsigned int euler          : 1; /// Bit de camino euleriano
  unsigned int hamilton       : 1; /// Bit de camino hamiltoniano
  unsigned int spanning_tree  : 1; /// Bit de �rbol abarcador
  unsigned int build_subtree  : 1; /// Bit de subgrafo

      /// Constructor por omisi�n que inicia todos los bits en cero
  Bit_Fields() 
    : depth_first(0), breath_first(0), test_cycle(0), find_path(0), 
      kruskal(0), prim(0), dijkstra(0), euler(0), hamilton(0), 
      spanning_tree(0), build_subtree(0)
  { /* empty */ }
  
  const bool get_bit(const int& bit) const
    {
      switch (bit)
        {
        case Depth_First: return depth_first;
        case Breath_First: return breath_first;
        case Test_Cycle: return test_cycle;
        case Is_Acyclique: return is_acyclique;
        case Test_Path: return test_path;
        case Find_Path: return find_path;
        case Kruskal: return kruskal;
        case Prim: return prim;
        case Dijkstra: return dijkstra;
        case Euler: return euler;
        case Hamilton: return hamilton;
        case Spanning_Tree: return spanning_tree;
        case Build_Subtree: return build_subtree;
        default:
          throw std::out_of_range("bit number out of range");
        }
    }
  void set_bit(const int& bit, const int& value) 
    {
      I(value == 0 or value == 1);

      switch (bit)
        {
        case Depth_First: depth_first = value; break;
        case Breath_First: breath_first = value; break;
        case Test_Cycle: test_cycle = value; break;
        case Is_Acyclique: is_acyclique = value; break;
        case Test_Path: test_path = value; break;
        case Find_Path: find_path = value; break;
        case Kruskal: kruskal = value; break;
        case Prim: prim = value; break;
        case Dijkstra: dijkstra = value; break;
        case Euler: euler = value; break;
        case Hamilton: hamilton = value; break;
        case Spanning_Tree: spanning_tree = value; break;
        case Build_Subtree: build_subtree = value; break;
        default:
          throw std::out_of_range("bit number out of range");
        }
    }
  void reset(const int& bit) { set_bit(bit, 0); }

  void reset()
  {
    depth_first = 0; 
    breath_first = 0; 
    test_cycle = 0; 
    is_acyclique = 0; 
    test_path = 0; 
    find_path = 0; 
    kruskal = 0; 
    prim = 0; 
    dijkstra = 0; 
    euler = 0; 
    hamilton = 0; 
    spanning_tree = 0; 
    build_subtree = 0; 
  }
};

    template <typename Node_Info> 
struct Graph_Node : public Dlink
{
  typedef Graph_Node Node;

  typedef Node_Info Node_Type;

  friend class Arc_Node;

  Node_Info  node_info;
  long       num_arcs;
  Dlink      arc_list; 
  Bit_Fields control_bits;
  long       counter;
  void *     cookie; 

  Node_Info & get_info() { return node_info;} 

  Graph_Node() : num_arcs(0), counter(No_Visited), cookie(NULL)
  { /* empty */ }

  Graph_Node(const Node_Info & info) 
    : node_info(info), num_arcs(0), counter(No_Visited), cookie(NULL) 
  { 
    /* empty */ 
  }

  Graph_Node(Graph_Node * node) 
    : node_info(node->get_info()), num_arcs(0), 
      counter(No_Visited), cookie(NULL) 
  { 
    /* empty */ 
  }
};


    template <typename Arc_Info> 
struct Graph_Arc : public Dlink    
{
  typedef Graph_Arc Arc;

  typedef Arc_Info Arc_Type; 

  Arc_Info   arc_info;

  void *     src_node;
  void *     tgt_node;

  Arc_Node * src_arc_node; // puntero al Arc_Node del nodo fuente
  Arc_Node * tgt_arc_node; // puntero al Arc_Node del nodo destino

  Bit_Fields control_bits;
  long       counter;
  void *     cookie; 

  void * get_connected_node(void * node)
  {
    return node == src_node ? tgt_node : src_node;
  }

  Arc_Info & get_info() { return arc_info; }

  Graph_Arc() : 
    src_node(NULL), tgt_node(NULL), src_arc_node(NULL), tgt_arc_node(NULL), 
    counter(No_Visited), cookie(NULL)
  { 
    /* empty */ 
  }

  Graph_Arc(const Arc_Info & info) : 
    arc_info(info), src_node(NULL), tgt_node(NULL), 
    src_arc_node(NULL), tgt_arc_node(NULL), 
    counter(No_Visited), cookie(NULL)
  { 
    /* empty */ 
  }

  Graph_Arc(void * src, void * tgt, const Arc_Info & data) :
    arc_info(data), src_node(src), tgt_node(tgt), src_arc_node(NULL), 
    tgt_arc_node(NULL), counter(No_Visited), cookie(NULL)
  { 
    I(src_node != NULL);
    I(tgt_node != NULL);
  }
};


struct Arc_Node : public Dlink
{
  void * arc;

  Arc_Node() : arc(NULL) { /* empty */ }

  Arc_Node(void * __arc) : arc(__arc) { /* empty */ }
};

    template <typename GT> 
class Path
{
public:

  typedef typename GT::Node_Type Node_Type;
  typedef typename GT::Arc_Type Arc_Type;

private:

  typedef typename GT::Node Node;
  typedef typename GT::Arc Arc;

  struct Path_Desc
  {
    Node * node;
    Arc *  arc;

    Path_Desc(Node * _node = NULL, Arc * _arc = NULL) 
      : node(_node), arc(_arc) {}
  };

  GT *                g;
  DynDlist<Path_Desc> list;

public:

  const bool inside_graph(GT & gr) const { return g == &gr; }

  Path(GT & _g) : g(&_g) { /* empty */ }

  Path() : g(NULL) { /* empty */ }

  const long & size() const { return list.size(); }

  const bool is_empty() const { return list.is_empty(); }

  void init(Node * start_node)
  {
    I(g->node_in_graph(start_node));
    
    list.append(Path_Desc(start_node));
  }

  Path(GT & _g, Node * start_node) : g(&_g)
  {
    init(start_node);
  }

  Path(const Path & path) : g(path.g), list(path.list) { /* empty */ }

  Path& operator = (const Path & path)
  {
    if (this == &path)
      return *this;

    clear_path();

    g = path.g;
    list = path.list;

    return *this;
  }

  void clear_path()
  {
    while (not list.is_empty())
      list.remove_first();
  }

  void append(Arc * arc)
  {
    Path_Desc & last_path_desc = list.get_last(); // ultimo elemento de list

    I(last_path_desc.arc == NULL);

    if (not g->node_belong_to_arc(arc, last_path_desc.node))
      throw std::invalid_argument("last node in path does "
                                  "not incide on arc");

    last_path_desc.arc = arc;

    list.append(Path_Desc(g->get_connected_node(arc, last_path_desc.node)));
  }

  void append(Node * node)
  {
    if (not g->node_in_graph(node))
      throw std::domain_error("node does not belong to graph");

    Node * last_node = get_last_node();

    Arc * arc = g->search_arc(last_node, node); // busque arco last_node-node

    if (arc == NULL)
      throw std::domain_error("There is no arc connecting node");

    append(arc);
  }

  Node * get_first_node() { return list.get_first().node; }

  Node * get_last_node() { return list.get_last().node; }

  Arc * get_first_arc() { return list.get_first().arc; }

  Arc * get_last_arc()
  {
    if (list.is_unitarian())
      throw std::domain_error("Path with only a node");

    typename DynDlist<Path_Desc>::Iterator it(list);
    it.reset_last();
    it.prev();

    return it.get_current().arc; 
  }

  const bool is_cycle() const { return get_first_node() == get_last_node(); }

  void remove_last_node()
  {
    list.remove_last();
    list.get_last().arc = NULL;
  }


  struct Iterator : public DynDlist<Path_Desc>::Iterator
  {
    Iterator() { /* empty */ }

    Iterator(Path& path) : DynDlist<Path_Desc>::Iterator(path.list) { }

      Iterator(const Iterator& it) : DynDlist<Path_Desc>::Iterator(it) { }
      
      Iterator & operator = (const Iterator& it) 
      {
        DynDlist<Path_Desc>::Iterator::operator = (it);
        return *this;
      }

      Node * get_current_node() { return this->get_current().node; }

      Arc * get_current_arc() { return this->get_current().arc; }
    };

  template <class Operation> void operate_nodes()
  {
    for (Iterator it(*this); it.has_current(); it.next())
      Operation () (*this, it.get_current_node());
  }

  template <class Operation> void operate_nodes(void * ptr)
  {
    for (Iterator it(*this); it.has_current(); it.next())
      Operation(ptr) (*this, it.get_current_node());
  }

  template <class Operation> void operate_arcs()
  {
    for (Iterator it(*this); it.has_current(); it.next())
      Operation () (*this, it.get_current_arc());
  }

  template <class Operation> void operate_arcs(void * ptr)
  {
    for (Iterator it(*this); it.has_current(); it.next())
      Operation(ptr) (*this, it.get_current_arc());
  }
}; 

    template <class GT> inline static
const bool __find_path(GT& g, 
                       typename GT::Node * current_node, // nodo procedencia
                       typename GT::Arc *  current_arc,  // arco de procedencia
                       typename GT::Node * end_node,     // nodo destino
                       typename GT::Path & current_path  // camino actual
                       )
{
  I(current_node not_eq NULL and current_arc not_eq NULL and 
         end_node not_eq NULL);
  I(g.node_belong_to_arc(current_arc, current_node));
  
  if (current_node == end_node) // se alcanz� nodo final?
    { 
      current_path.append(current_arc); // a�adir �ltimo arco al camino

      return true;
    }

  if (IS_NODE_VISITED(current_node, Aleph::Find_Path))
    return false; // ya pasamos por este nodo ==> desde �l no hay camino

  current_path.append(current_arc); // a�adir arco al camino

  NODE_BITS(current_node).set_bit(Aleph::Find_Path, true); // marcar nodo

      // buscar recursivamente a trav�s de arcos de current_node
  for (typename GT::Node_Arc_Iterator itor(current_node); 
       itor.has_current(); itor.next())
    {
      typename GT::Arc * next_arc = itor.get_current_arc();
      
      if (IS_ARC_VISITED(next_arc, Aleph::Find_Path))
        continue; // ya se pas� por este arco 

      ARC_BITS(next_arc).set_bit(Aleph::Find_Path, true); // marcar arco

      typename GT::Node * next_node = itor.get_tgt_node(); 

      if (IS_NODE_VISITED(next_node, Aleph::Find_Path))
        continue; // se alcanz� un nodo ya visitado desde otro arco

          // continuamos exploraci�n en profundidad desde next_node
      if (__find_path<GT>(g, next_node, next_arc, end_node, current_path))
        {
          I(current_path.get_last_node() == end_node);

          return true; // se encontr� camino, terminar retornando true
        }
    }

      // no se encontr� camino por este arco ==> eliminarlo de path
  current_path.remove_last_node();

  return false;
}
    template <class GT> inline 
const bool find_path(GT& g, 
                     typename GT::Node * start_node, 
                     typename GT::Node * end_node,
                     typename GT::Path & path)
{
  I(g.node_in_graph(start_node));
  I(g.node_in_graph(end_node));

  if (not path.inside_graph(g))
    throw std::invalid_argument("Path does not belong to graph");

  path.clear_path(); // limpiamos cualquier cosa que est� en path

  path.init(start_node); // insertamos nodo origen

      // verificamos si se busca un ciclo
  if (start_node == end_node)
    { // buscar un arco simple hacia si mismo. Ahorra calculo si ese es el caso
      for (typename GT::Node_Arc_Iterator itor(start_node); 
           itor.has_current(); itor.next())

        if (itor.get_current_arc()->get_connected_node(start_node) == end_node)
          return true;

      return false;
    }
     
  g.reset_bit_nodes(Aleph::Find_Path);
  g.reset_bit_arcs(Aleph::Find_Path); 

      //marcamos start_node visitado
  NODE_BITS(start_node).set_bit(Aleph::Find_Path, true); 

      // buscar para cada arco de start_node
  for (typename GT::Node_Arc_Iterator itor(start_node); 
       itor.has_current(); itor.next())
    {
      typename GT::Arc * arc = itor.get_current_arc();

      if (IS_ARC_VISITED(arc, Aleph::Find_Path))
        continue; /* ya se paso por este arco */

          // marcar arco como visitado
      ARC_BITS(arc).set_bit(Aleph::Find_Path, true); 

      typename GT::Node * next_node = itor.get_tgt_node();

      if (IS_NODE_VISITED(next_node, Aleph::Find_Path))
        continue; /* se alcanza un nodo ya visitado desde otro
                     arco. Descartar porque ya buscamos por este
                     nodo. Hay un ciclo */

      if (__find_path(g, next_node, arc, end_node, path))
        {
          I(path.get_first_node() == start_node and 
            path.get_last_node() == end_node);

          return true;
        }
    }

  return false;
}

    template <typename __Graph_Node, typename __Graph_Arc>
class List_Graph
{
public:

  typedef __Graph_Node Node;

  typedef __Graph_Arc Arc;

  typedef typename Node::Node_Type Node_Type; 

  typedef typename Arc::Arc_Type Arc_Type;

  typedef Path< List_Graph<Node, Arc> > Path;

  private:

    Dlink node_list; // lista de nodos
    long  num_nodes; // cantidad de nodos

    Dlink arc_list;  // lista de arcos
    long  num_arcs; // cantidad de arcos

      // convierte un Dlink* base de Node (pasado como par�metro de
      // List_Graph) a un Node. Debe haberse obtenido de node_list
  static Node * dlink_to_node(Dlink * p)
  {
    return static_cast<Node*>(p);
  }

      // convierte un Dlink* base de Arc (pasado como par�metro de
      // List_Graph) a un Arc. Debe haberse obtenido de arc_list
  static Arc * dlink_to_arc(Dlink * p)
  {
    return static_cast<Arc*>(p);
  }

      // Concierte un Dlink* base de Arc_Node a un Arc_Node. Debe haberse
      // obtenido  desde Node::arc_list 
  static Arc_Node * dlink_to_arc_node(Dlink * p)
  {
    return static_cast<Arc_Node*>(p);
  }

  static Arc * arc_node_to_arc(Arc_Node * arc_node)
  {
    return static_cast<Arc*>(arc_node->arc);
  }

public:

  const long get_num_nodes() const { return num_nodes; }

  const long get_num_arcs() const { return num_arcs; }

  Node * get_first_node() 
  {
    if (get_num_nodes() == 0)
      throw std::range_error("Graph has not nodes");

    return dlink_to_node(node_list.get_next());
  }

  Arc * get_first_arc() 
  {
    if (get_num_arcs() == 0)
      throw std::range_error("Graph has not arcs");

    return dlink_to_arc(arc_list.get_next());
  }

  // m�todos que manipulan nodos

  const long & get_num_arcs(Node * node) const { return node->num_arcs; }

  void reset_bit(Node * node, const int & bit) 
  {
    node->control_bits.reset(bit); 
  }

  Bit_Fields & get_control_bits(Node * node) { return node->control_bits; }

  void set_bit(Node * node, const int & bit, const int & value) 
  {
    node->control_bits.set_bit(bit, value);
  }

  long & get_counter(Node * node) { return node->counter; }

  void reset_counter(Node * node) { node->counter = No_Visited; }

  void *& get_cookie(Node * node) { return node->cookie; }


  // m�todos que manipulan arcos

  Node * get_src_node(Arc * arc) 
  {
    return static_cast<Node*>(arc->src_node); 
  }

  Node * get_tgt_node(Arc * arc) 
  { 
    return static_cast<Node*>(arc->tgt_node); 
  }

  Node * get_connected_node(Arc * arc, Node * node) 
  {
    return static_cast<Node*>(arc->get_connected_node(node));
  }

  const bool node_belong_to_arc(Arc * arc, Node * node) const
  {
    return node == arc->src_node or node == arc->tgt_node;
  }

  void reset_bit(Arc * arc, const int & bit) 
  {
    arc->control_bits.reset(bit); 
  }

  Bit_Fields & get_control_bits(Arc * arc) { return arc->control_bits; }

  void set_bit(Arc * arc, const int & bit, const int & value) 
  {
    arc->control_bits.set_bit(bit, value);
  }

  long & get_counter(Arc * arc) { return arc->counter; }

  void reset_counter(Arc * arc) { arc->counter = No_Visited; }

  void *& get_cookie(Arc * arc) { return arc->cookie; }


  void clear_graph()
  {
        // recorrer cada nodo del grafo a~trav�s de la lista de nodos
    for (Dlink::Iterator node_itor(&node_list); node_itor.has_current(); )
      {
        Dlink * l = node_itor.get_current(); // obtener dlink del nodo actual
        Node * p  = dlink_to_node(l);  // convertirlo a Node*

            // avanzar antes de borrar para que iterador siga consistente
        node_itor.next();

        remove_node(p); 
      }

    I(num_nodes == 0 and num_arcs == 0);
  }

  protected:
    bool digraph;

  public:

    void verify_graphs(List_Graph& g)
    {
      if (digraph and not g.digraph)
        throw std::domain_error("List_Graph and List_Digraph combined");
    }

  const bool is_digraph() const { return digraph; }

  class Node_Iterator : public Dlink::Iterator
  {
    List_Graph * g;

  public:

    Node_Iterator() : g(NULL) { /* empty */ }

    Node_Iterator(List_Graph & _g) : Dlink::Iterator(&_g.node_list), g(&_g)
    {
      // empty
    }

    Node_Iterator(const Node_Iterator & it) : Dlink::Iterator(it), g(it.g)
    {
      // empty
    }

    Node_Iterator & operator = (const Node_Iterator & it) 
    {
      Dlink::Iterator::operator = (it);
      g = it.g;
        
      return *this;
    }

    Node * get_current_node() { return dlink_to_node(get_current()); }
  };

  class Arc_Iterator : public Dlink::Iterator
  {
    List_Graph * g;

  public:

    Arc_Iterator() : g(NULL) { /* empty */ }

    Arc_Iterator(List_Graph & _g) : Dlink::Iterator(&_g.arc_list), g(&_g)
    {
      // empty
    }

    Arc_Iterator(const Arc_Iterator & it) : Dlink::Iterator(it), g(it.g)
    {
      // empty
    }

    Arc_Iterator & operator = (const Arc_Iterator & it) 
    {
      Dlink::Iterator::operator = (it);
      g = it.g;

      return *this;
    }

    Arc * get_current_arc() { return dlink_to_arc(get_current()); }
  };

  class Node_Arc_Iterator : public Dlink::Iterator
  {
    Node * src_node; 

    Arc_Node * get_current_arc_node() 
    {
      return static_cast<Arc_Node*>(get_current());
    }

  public:

    Node_Arc_Iterator() : src_node(NULL) { /* empty */ }

    Node_Arc_Iterator(Node * _src_node) 
      : Dlink::Iterator(&(_src_node->arc_list)), src_node(_src_node)
    {
      // empty
    }

    Node_Arc_Iterator(const Node_Iterator& it) 
      : Dlink::Iterator(it), src_node(it.src_node) 
    { 
      /* empty */ 
    }
                
    Node_Arc_Iterator & operator = (const Node_Iterator& it) 
    {
      Dlink::Iterator::operator = (it);

      src_node = it.src_node;

      return *this;
    }

    Arc * get_current_arc() 
    {
      return static_cast<Arc*>(get_current_arc_node()->arc);
    }

    Node * get_tgt_node() 
    { 
      return 
	static_cast<Node*>(get_current_arc()->get_connected_node(src_node));
    }
  };

  List_Graph() : num_nodes(0), num_arcs(0), digraph(false)
  { /* empty */ }

  List_Graph(const List_Graph & g) : num_nodes(0), num_arcs(0), digraph(false)
  {
    copy_graph(const_cast<List_Graph&>(g));
  }

  List_Graph& operator = (List_Graph & g)
  {
    if (this == &g)
      return *this;

    copy_graph(const_cast<List_Graph&>(g));

    return *this;
  }

  virtual ~List_Graph() { clear_graph(); }

  inline List_Graph(List_Digraph<Node, Arc> & dg);

  inline List_Graph & operator = (List_Digraph<Node, Arc> & dg);

  void insert_node(Node * node)
  {
    I(node != NULL);
    I(not node_in_graph(node));
    
    ++num_nodes;
    node_list.append(node);
  }

  Node * insert_node(const Node_Type & node_info)
  {
    Node * ret_val = new Node (node_info);

    insert_node(ret_val);

    return ret_val;
  }

  Arc * insert_arc(Node *           src_node, 
                   Node *           tgt_node, 
                   const Arc_Type & arc_info)
  {
    I(node_in_graph(src_node)); // debe haber sido previamente insertado
    I(node_in_graph(tgt_node)); // debe haber sido previamente insertado

        // apartar memoria para arco global 
    //    auto_ptr<Arc> arc ( new Arc (src_node, tgt_node, arc_info) );

    auto_ptr<Arc> arc ( new Arc()  );

    arc->src_node  = src_node;
    arc->tgt_node  = tgt_node;
    arc->get_info() = arc_info;
          
        // apartar Arc_Node para src_node 
    auto_ptr<Arc_Node> src_arc_node ( new Arc_Node (arc.get()) );
      
    if (not digraph) // si es digrafo ==> no hay que insertar en el otro nodo
      {     // inserci�n en nodo destino 

        if (src_node == tgt_node) // verificar si se trata de un ciclo
          arc->tgt_arc_node = src_arc_node.get(); /* este es un ciclo */
        else
          {     // apartar arco nodo para tgt_node 
            auto_ptr<Arc_Node> tgt_arc_node ( new Arc_Node (arc.get()) ); 

              // inserci�n en nodo destino 
            arc->tgt_arc_node = tgt_arc_node.get();    
            ARCS_LIST(tgt_node).append(tgt_arc_node.get());
            ++NUM_ARCS(tgt_node);
            tgt_arc_node.release(); // desbloquear tgt_arc_node
          }
      }

        // insertar en lista de arcos del grafo 
    arc_list.append(arc.get());
    ++num_arcs;

        // inserci�n en nodo origen 
    arc->src_arc_node = src_arc_node.get();
    ARCS_LIST(src_node).append(src_arc_node.get());
    ++NUM_ARCS(src_node);

    src_arc_node.release(); // desbloquear tgt_arc_node

    return arc.release(); // desbloquear arc
  }

  void remove_arc(Arc * arc)
  {
    I(arc != NULL);
    I(arc_in_graph(arc));

          /* eliminaci�n de arco en nodo origen */
    Node * src_node = get_src_node(arc); 
    Arc_Node * src_arc_node = arc->src_arc_node;
    src_arc_node->del();  // desenlaza src_node de la lista de nodos
    --NUM_ARCS(src_node);
    delete src_arc_node;  

    if (not digraph) 
      {     /* eliminaci�n arco en nodo destino */
        Node * tgt_node = get_tgt_node(arc);
        if (src_node != tgt_node) /* verificar eliminaci�n de ciclo */
          { 
            Arc_Node * tgt_arc_node = arc->tgt_arc_node;
            tgt_arc_node->del(); 
            --NUM_ARCS(tgt_node);
            delete tgt_arc_node;
          }
      }
          /* eliminaci�n de arco del grafo */
    arc->del(); // desenlazar arc de la lista de arcos del grafo
    --num_arcs;
    delete arc;
  }

  void remove_node(Node * node)
  {
    I(node != NULL);
    I(node_in_graph(node));

        /* mientras haya arcos en el nodo */
    while (not ARCS_LIST(node).is_empty())
      {
	    // obtener enlace Arc_Node
        Dlink * arc_link = ARCS_LIST(node).get_next(); 

        Arc_Node * arc_node = dlink_to_arc_node(arc_link);

        Arc * arc = arc_node_to_arc(arc_node);

        remove_arc(arc); // eliminar el arco
      }

    node->del(); // desenlazar nodo de lista de nodos del grafo
    --num_nodes;

    delete node; 
  }

  void reset_bit_nodes(const int & bit)
  {
    for (Node_Iterator itor(*this); itor.has_current(); itor.next())
      reset_bit(itor.get_current_node(), bit);
  }

  void reset_bit_arcs(const int & bit)
  {
    for (Arc_Iterator itor(*this); itor.has_current(); itor.next())
      reset_bit(itor.get_current_arc(), bit);
  }

  void reset_counter_nodes()
  {
    for (Node_Iterator itor(*this); itor.has_current(); itor.next())
      reset_counter(itor.get_current_node());
  }

  void reset_counter_arcs()
  {
    for (Arc_Iterator itor(*this); itor.has_current(); itor.next())
      reset_counter(itor.get_current_arc());
  }

  template <class Operation> void operate_nodes()
  {
    for (Node_Iterator itor(*this); itor.has_current(); itor.next())
      Operation () (*this, itor.get_current_node());
  }

  template <class Operation> void operate_arcs()
  {
    for (Arc_Iterator itor(*this); itor.has_current(); itor.next())
      Operation () (*this, itor.get_current_arc());
  }

  template <class Operation> void operate_nodes(void * ptr)
  {
    for (Node_Iterator itor(*this); itor.has_current(); itor.next())
      Operation (ptr) (*this, itor.get_current_node());
  }

  template <class Operation> void operate_arcs(void * ptr)
  {
    for (Arc_Iterator itor(*this); itor.has_current(); itor.next())
      Operation (ptr) (*this, itor.get_current_arc());
  }

  template <class Operation> void operate_arcs(Node * node)
  {
    for (Node_Arc_Iterator it(node); it.has_current(); it.next())
      Operation () (*this, it.get_current_arc());
  }

  template <class Operation> void operate_arcs(Node * node, void * ptr)
  {
    for (Node_Arc_Iterator it(node); it.has_current(); it.next())
      Operation (ptr) (*this, it.get_current_arc());
  }

private:

  struct Reset_Node
  {
    void operator () (List_Graph&, Node * node)
    {
      node->control_bits.reset();
      node->counter = 0;
      node->cookie = NULL;
    }
  };

public:

  void reset_nodes()
  {
    operate_nodes <Reset_Node> ();
  }

private:

  struct Reset_Arc
  {
    void operator () (List_Graph&, Arc * arc)
    {
      arc->control_bits.reset();
      arc->counter = 0;
      arc->cookie = NULL;
    }
  };

public:

  void reset_arcs()
  {
    operate_arcs<Reset_Arc> ();
  }

      template <class Equal>
  Node * search_node(const Node_Type & node_info)
  {
    for (Node_Iterator itor(*this); itor.has_current(); itor.next())
      {
        Node * current_node = itor.get_current_node();
        
        if (Equal() (current_node->get_info(), node_info))
          return current_node;
      }

    return NULL;
  }

  Node * search_node(const Node_Type & node_info)
  {
    return search_node<Aleph::equal_to<Node_Type> >(node_info);
  }

  Arc * search_arc(Node * src_node, Node * tgt_node) 
  {
    if (src_node == NULL or tgt_node == NULL)
      return NULL;

    I(node_in_graph(src_node));
    I(node_in_graph(tgt_node));

    Node_Arc_Iterator itor;
    
    Node * searched_node;

        // Seleccionar el nodo que contenga menor cantidad de arcos
    if (digraph or src_node->num_arcs < tgt_node->num_arcs)
      {
        searched_node = tgt_node;
        itor = Node_Arc_Iterator(src_node);
      }
    else
      {
        searched_node = src_node;
        itor = Node_Arc_Iterator(tgt_node);
      }

    while (itor.has_current())
      {
        if (itor.get_tgt_node() == searched_node)
          return itor.get_current_arc();

        itor.next();
      }

    return NULL; 
  }

      template <class Equal>
  Arc * search_arc(const Arc_Type & arc_info)
  {
    for (Arc_Iterator it(*this); it.has_current(); it.next())
      {
        Arc * current_arc = it.get_current_arc();
        
        if (Equal() (current_arc->get_info(), arc_info))
          return current_arc;
      }    

    return NULL; 
  }

  Arc * search_arc(const Arc_Type & arc_info)
  {
    return search_arc<Aleph::equal_to<Arc_Type> >(arc_info);
  }

  const bool node_in_graph(Node * node)
  {
    I(node != NULL);

    for (Node_Iterator it(*this); it.has_current(); it.next())
      {
        Node * current_node = it.get_current_node();

        if (current_node == node)
          return true;
      }

    return false;
  }

  const bool arc_in_graph(Arc * arc) 
  {
    I(arc != NULL);

    for (Arc_Iterator it(*this); it.has_current(); it.next())
      if (it.get_current_arc() == arc)
        return true;

    return false;
  }

      template <class Compare>
  void sort_arcs()
  {
    DynArray<Arc*> arc_array; // arreglo temporal donde guardar los arcos

        // copiar arcos al arreglo din�mico a la vez que se vac�a la lista
    for (int i = 0; not arc_list.is_empty(); ++i)
      {
        Arc * arc = dlink_to_arc(arc_list.remove_next());
        arc_array[i] = arc;
      }

      quick_sort<Arc*, Compare>(arc_array); // ordenar arreglo

        // regresarlos a la lista en orden
    for (int i = 0; i < num_arcs; ++i)
      {
        Arc * arc = arc_array[i];
        arc_list.append(arc);
      }
  }

  void copy_graph(List_Graph & src_graph)
    {
      IG(not is_digraph() and src_graph.is_digraph(), 
         is_digraph() != src_graph.is_digraph());

      verify_graphs(src_graph);
      try
        {
          clear_graph(); // limpiar this antes de copiar

              // mapeo de nodos de origen a destino
          DynAvlTree<Node*, Node*> tree; 

              // recorrer todos los nodos de grafo src_graph
          for (Node_Iterator it(src_graph); it.has_current(); it.next())
            {
              Node * src_node = it.get_current_node(); 

              auto_ptr<Node> tgt_node(new Node(src_node)); // hacer una copia

              tree.insert(src_node, tgt_node.get()); // insertarla en mapeo avl

              insert_node(tgt_node.release()); // insertarla en grafo destino
            }

          I(get_num_nodes() == src_graph.get_num_nodes());

              // recorrer todos los arcos de src_graph
          for (Arc_Iterator it(src_graph); it.has_current(); it.next())
            {
              Arc * src_arc = it.get_current_arc();

                  // obtener im�genes de nodos en el grafo destino 
              Node * src_node = tree[src_graph.get_src_node(src_arc)]; 
              Node * tgt_node = tree[src_graph.get_tgt_node(src_arc)];

                  // insertar arco en grafo destino
              insert_arc(src_node, tgt_node, src_arc->get_info()); 
            }

          I(get_num_arcs() == src_graph.get_num_arcs());
        }
      catch (...)
        { // limpia los parcialmente copiad en tgt_graph 
          clear_graph(); 
          throw;
        }
    }
};

    template <typename Node_Info, typename Arc_Info>
struct List_Digraph : public List_Graph<Node_Info, Arc_Info>
{
  List_Digraph() 
  {
    List_Graph<Node_Info, Arc_Info>::digraph = true;
  }

  List_Digraph(const List_Digraph & dg) : List_Graph<Node_Info, Arc_Info>(dg)
  {
    List_Graph<Node_Info, Arc_Info>::digraph = true; 
  }

  List_Digraph & operator = (List_Digraph& dg)
  {
    if (&dg == this)
      return *this;

    copy_graph(*this, dg);
  }
};





} // end namespace Aleph

# endif /* TPL_LIST_GRAPH_H */
